//按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
//
// n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
//
// 给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
//
//
//
// 每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
//
//
//
//
//
// 示例 1：
//
//
//输入：n = 4
//输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
//解释：如上图所示，4 皇后问题存在两个不同的解法。
//
//
// 示例 2：
//
//
//输入：n = 1
//输出：[["Q"]]
//
//
//
//
// 提示：
//
//
// 1 <= n <= 9
//
//
// Related Topics 数组与矩阵 回溯与递归 👍 1753 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
function solveNQueens(n: number): string[][] {


    function backtracking(row,board) {
        if (row === n) {
            let temp : string[] = []
            for (let i = 0; i < n; i ++) {
                temp.push(board[i].join(''))
            }
            res.push(temp)
            return
        }
        for (let i = 0; i < n; i ++) {
            if (judge(i,row,board)) {
                board[row][i] = 'Q'
                backtracking(row + 1, board)
                board[row][i] = '.'
            }

        }
    }
    //? 条件判断
    function judge(col,row,board) {
        if (col >= n || row >= n || col < 0 || row < 0) return false
        for (let i = 0; i < n; i ++) {
            if (board[i][col] === 'Q') {
                return false
            }
        }
        let x : number
        let y : number
        x = row
        y = col
        //? 判断左下
        while (x >= 0 && y < n) {
            if (board[x][y] === 'Q') return false
            x --
            y ++
        }
        x = row
        y = col
        //? 判断右下
        while (x >= 0 && y >= 0) {
            if (board[x][y] === 'Q') return false
            x --
            y --
        }

        return true
    }
    let res : string[][] = []
    let board : string[][] = new Array(n).fill(0).map(()=>new Array(n).fill('.'))
    backtracking(0, board)
    return res
};
//leetcode submit region end(Prohibit modification and deletion)
